stack
concept of stack
A type of linear data structure
Last In First Out (LIFO) Structure
stacked-up structure
Elements that come in later come out first.
Stack features
Data of the same size and of the same structure can be stacked only in a fixed direction, and can only be accessed through the place designated by the top.
Deletion is possible only through top.
operation on the stack
Delete (pop()): Removes the topmost item from the stack. [O(1)]
Insert (push(item)): Adds an item to the top of the stack. [O(1)]
read (peek()) : Returns the topmost item on the stack. [O(1)]
Stack Pointer (SP)
When pushing or popping, you need to know the location of the value, but the stack pointer remembers the location.
Initial default is -1
ex) push
ex) pop
Stack usage example
Web Browser History (Go Back): Shows the page that was last opened again.
Reverse order string creation: Outputs the last inputted character first.
Undo (undo): Undo the last executed action.
Postfix notation calculation
recursive function
Queue
concept of queue
A type of linear data structure
First In First Out (FIFO) architecture
The element that enters first comes out first.
A structure in which the element that enters first waits at the front and comes out first
In Java Collection, Queue is an interface.
queue characteristics
The first element is called front and the last element is called rear.
Only the first and last elements are accessible.
Queue operation
Insert (Enqueue()) : Add an element to the end of the queue [O(1)]
Delete (Dequeue()) : Deletes the element at the front of the queue [O(1)]
Read (peek()) : Read data located in front [O(n)]
front and rear
When inserting and subtracting data, it is necessary to remember the position of the corresponding value. (acts like a stack pointer)
front: See the front position (index) of the queue.
rear : See the position (index) at the back of the queue.
Problems with linear queues
If the queue is full of data, no more data can be added.
As we iterate through insertions and deletions in the linear queue, we recognize that rear points to the very last index, which may be empty in front, but is full.
(Since rear is at the last position in the array, even if there are empty seats in the queue, it is recognized as saturated and no insert operation is performed.)
This is because the actual data was not moved forward one space each time it was deleted, and queue operation was performed in units of index.
To prevent this, Circular Queue exists.
round queue
Logically, the beginning and the end of an array are considered to be connected.
In the initial blank state, front and rear are 0
One digit is always left blank to easily distinguish between blank and saturated state (size +1).
When adding data, the rear moves 1 space, and when deleting data, the front moves 1 space.
rear = (rear + 1) move by % size.
When rear is 7, since there must be at least one blank, it is recognized as saturated and no data is inserted.
front= (front + 1) move by % size.
Data can be added because space is left.
heap
concept of heap
A kind of complete binary tree (a data structure designed to quickly find the maximum and minimum values among multiple values)
Data structures created for priority queues
A data structure designed to quickly find the maximum or minimum value among multiple values as a kind of tree.
Big O: O(logn)
- Priority queue
Data has priority, and data with higher priority goes out first.
CPU task scheduling, used in simulation systems
type of heap
max heap
A complete binary tree in which the parent node's key value is greater than or equal to the child node's key value.
key (parent node) ≥ key (child node)
min heap
A complete binary tree in which the parent node's key value is less than or equal to the child node's key value.
key (parent node) ≤ key (child node)
Heap Features
The standard data structure to store the heap is an array.
Duplicate values are allowed.
Keep it half-aligned.
heap operation
insertion
When a new element enters the heap, the new node is inserted into the last node of the heap.
Exchange new node with parent node
delete
In max heap, max is the root node, so root node is deleted (in max heap, delete operation is to delete max element)
The deleted root node gets the last node in the heap.
rebuild the heap
