Ordered Data Structures # WEEK 1 - Queue & Stack

queue와 stack은 array와 linked list와 같은 primitive 선상의 데이터 구조보다는 좀 더 상위인듯.

둘 다, array기반, linked list 기반으로 구현할 수 있음.

queue를 linked list로 구현할 때는 tail pointer의 개념을 사용해 이중연결리스트.

stack을 linked list로 구현할 때는 null pointer 싱글연결리스트로 가능.

 

1.5 Queue

A queue is a first-in first-out data structure that is similar to waiting in a line or "queue";

waiting in line for a cup of coffee, the first person who arrive in the line will get their drink first.

 

Abstract Data Type

In data structures, we will always begin our analysis asking "how can this structure be used with data?"

• A structure's Abstract Data Type(ADT) is how data interacts with the structure
• *An ADT is not an implementation(구현), it is a description(하는 일에 대한 설명)

queue를 가지고 어떤 일을 할 수 있는지, 역할이 무엇인지에 대한 설명인듯.

 

Queue ADT

create	Creates an empty queue
push	Adds data to the back of the queue
pop	Removes data from the front of the queue
empty	Returns true if the queue is empty

 

Example

 

Consider four operation:

• Create a queue of integers.
• Push the number 4 to the queue.
• Push the number 2 to the queue.
• Pop a number from the queue.

 

Implementation

 

Let's understand what the queue does internally and how fast it runs. Internally queue can be implemented with either of our two basic data types that we've already discussed.

 

• array-based queue
  • can keep track index
  • fixed initial size
  • There's a number of different ways to set up the arrays, but so long as you keep track of where the insertion point is and where the removal point is or where the pop and push points are, we can always just adjust them by adding one or subtracting one and resizing the array as needed. All of these operations are just operation of indices(인덱스) and are always going to run in O of one time.
• linked list based queue
  • tail pointer that's maintained the very end of the list. This tail pointer will allow us to always access the last element of list. tail pointer is, in link memory, instead of just linking our memory forward, let's make sure we link all of our memory backwards as well.
  • when a new element arrives, we can always add it directly to the head. we know that adding to the head takes O of one time. On the other side, when we have a tail pointer, we can always find the element at the very end in O of one time. * head에 계속 push하고 tail pointer를 통해 마지막 요소에 접근가능

 

정리하자면

 

A queue is a first-in first-out data structure that is similar to waiting in a line.

 

A queue may be implemented with an array or a doubly-linked list

*both an array-baed and a list-based implementation can be built to run in constant, O(1) running time.

 

The sister data structure to the queue is the stack

---

1.6 Stack 

A stack is a last-in first -out data structure that is similar to a pile("stack") of papers.

Stack ADT

create	Creates an empty stack
push	Adds data to the top of the stack
pop	Removes data from the top of the stack
empty	Returns true if the stack is empty

 

Example

Consider four operation:

• Create a stack of integers.
• Push the number 4 to the stack
• Push the number 2 to the stack
• Pop a number from the stack

 

Implementation

• Array-based
  • 배열이 꽉 찼을 때 배열 크기를 두 배로 늘리는 방법
• Linked-list based
  • Linked list is even easier. when the stack is initially empty we're going to have a links list that simply points to null. When we add our first element, we simply update the front of the list. And add that element. When we add a second element, we just insert at the front of the list again.

배열 다 차면 resize

 

queue와 달리 tail pointer를 사용할 필요가 없기 때문에 single linked list면 충분하다.

 

Stack

A stack is a last-in first-out(LIFO) data structure that is similar to a pile("stack") of papaers.

 

A stack may be implemented with an array or a linked list.

*Both an array-based and a list-based implementation can be built to run in constant, O(1) running time.