One Paper: Stack & Queue

* 필요한 문장으로 판단되는 경우에 발췌했으며, 출처 표기를 준수하였습니다.

** 본 글은 개인 노션에서 가져왔습니다. 

 

 

1. Stack

• In computer science, a stack is an abstract data type that serves as a collection of elements, with two main pricipal operation(push, pop)

  • abstract data type is a mathematical model for data types.

  • An abstract data type is defined by its behavior (semantics) from the point of view of a user, of the data, specifically in terms of possible values, possible operations on data of this type, and the behavior of these operations.

    Example: abstract stack (functional) For example, a complete functional-style definition of an abstract stack could use the three operations: push: takes a stack state and an arbitrary value, returns a stack state; top: takes a stack state, returns a value; pop: takes a stack state, returns a stack state.

• The order in which elements come off a stack gives rise to its alternative name, LIFO(last in, first out).

• It is similar to a stack of plates, adding or removing is only possible at the top.

• Considered as a linear data structure, or more abstractly a sequential collection, the push and pop operations occur only at one end of the structure, referred to as the top of the stack.

• This data structure makes it possible to implement a stack as a singly linked list and a pointer to the top element.

• A stack may be implemented to have a bounded capacity. If the stack is full and does not contain enough space to accept an entity to be pushed, the stack is then considered to be in an overflow state. The pop operation removes an item from the top of the stack.

• A stack is needed to implement depth-first search.
•  

1.1 History

• Stacks entered the computer science literature in 1946, when Alan M. Turing used the terms "bury" and "unbury" as a means of calling and returning from subroutines. [3][4] Subroutines had already been implemented in Konrad Zuse's Z4 in 1945.

1.2 Software stacks

Implementation

• A stack can be easily implemented either through an array or a linked list. What identifies the data structure as a stack, in either case, is not the implementation but the interface: the user is only allowed to pop or push items onto the array or linked list, with few other helper operations.

1.3 Hardware stack

• A common use of stacks at the architecture level is as a means of allocating and accessing memory.

 

source: Stack (abstract data type)

1.4 Question: Working of Stack Data Structure

*바로 밑에 출처에 있는 글을 보았다. top이 당연히 (시작값 할당을) 0이라고 알고 있었는데 아니었다. queue 또한 아니었다. 과제에서도 stack: top, queue: front가 0이라고 되어있었는데 이런 의도가 궁금해서 질문을 남겼다.

질문: https://github.com/codestates/help-desk/issues/2197

질문 내용:

source: Stack Data Structure

2. Queue

• In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence.
• The operations of a queue make it a first-in-first-out (FIFO) data structure. In a FIFO data structure, the first element added to the queue will be the first one to be removed.
• Common implementations are circular buffers and linked lists.

 

 

source:Queue (abstract data type)

 

source: Queue Data Structure