Stack, Queue, Deque? What the?

A type of data structure that stores and manages data in various ways

 

Stack

[Definition]
 A stack, which means stacking data neatly, can only be accessed through the top, so both push and pop operations occur at the top. It follows a LIFO(Last In, First Out) structure, where the most recently added data is the first to be removed. While there may be cases where different data types are mixed depending on the programming language and implementation, it is generally composed of the same data type to ensure stability.

[Advantages]
 Stacks are implemented as lists, with each element added to the end of an array, allowing memory to be allocated only when necessary, making memory usage efficient. The inherent LIFO structure of stacks facilitates natural management during recursive function calls.
▲ Simple to implement and efficient in memory usage.
▲ Useful for function calls.

[Disadvantages]
 As part of the reserved memory space for program execution, stacks have a fixed size, leading to lightweight use within limited storage. Care must be taken to avoid stack overflow when attempting to store too much data in the stack. Access is only possible for the top data for quick memory allocation and deallocation.
▼ Limited storage space.
▼ No access to intermediate data.

[Applications]
 By leveraging the advantages of the LIFO mechanism, the most recent activity can be pushed onto the stack, and when needed, the last pushed operation can be popped to revert to the previous state.
▶ Backward navigation feature in web browsers
▶ Undo function

 

Queue

[Definition]
 Unlike a stack, a queue allows access from both ends. Insertion occurs only at the rear, while deletion happens only at the front. It follows a FIFO(First In, First Out) structure, where the data added first is the first to be removed.

[Advantages]
 Since data that enters first exits first, a queue is an effective data structure for scenarios like waiting lines.
▲ Fair processing of queue data.

 

[Disadvantages]
 Access is only possible through the front and rear, making it impossible to access intermediate data. Because insertion and deletion occur at both ends, performance degradation can be more pronounced, especially when dynamic memory allocation happens frequently.
▼ No access to intermediate data.
▼ Requires careful memory management.

[Applications]
 By utilizing the advantages of the FIFO mechanism, queues can manage and process various waiting situations in a sequential manner.
▶ Printer queue
▶ Process scheduling

 

Dequeue

[Definition]
 A deque(double-ended queue) can be understood as a queue without a fixed direction for insertion and deletion.

[Advantages]
 Since data can be accessed from both ends, deques offer high flexibility and provide the functionalities of both stacks and queues.
▲ Greater flexibility compared to stacks and queues.
▲ Simultaneously provides the functions of stacks and queues.

[Disadvantages]
 While there are many advantages, the implementation can be complex, and when implemented using a fixed-size array, memory usage may be inefficient.
▼ Implementation can be difficult.
▼ Inefficient memory usage may be a concern.

[Applications]
 With the ability to insert and delete data from both ends, deques can be efficiently used in sliding window scenarios or any situation requiring history management.
▶ Sliding window algorithm
▶ Priority management and sorting algorithms