10.1.md

Exercises 10.1-1

---

Using Figure 10.1 as a model, illustrate the result of each operation in the sequence PUSH(S, 4), PUSH(S, 1), PUSH(S, 3), POP(S), PUSH(S, 8), and POP(S) on an initially empty stack S stored in array S[1...6].

Answer

1	2	3	4	5	6
4

1	2	3	4	5	6
4	1

1	2	3	4	5	6
4	1	3

1	2	3	4	5	6
4	1

1	2	3	4	5	6
4	1	8

1	2	3	4	5	6
4	1

Exercises 10.1-2

---

Explain how to implement two stacks in one array A[1...n] in such a way that neither stack overflows unless the total number of elements in both stacks together is n. The PUSH and POP operations should run in O(1) time.

Answer

At the beginning, top of the first stack is A[1], top of the second stack - A[n]. When pushing element to first stack, increase the iterator, when pushing to the second stack - decrease it.

Exercises 10.1-3

---

Using Figure 10.2 as a model, illustrate the result of each operation in the sequence ENQUEUE(Q, 4), ENQUEUE(Q, 1), ENQUEUE(Q, 3), DEQUEUE(Q), ENQUEUE(Q, 8), and DEQUEUE(Q) on an initially empty queue Q stored in array Q[1...6].

Answer

1	2	3	4	5	6
4

1	2	3	4	5	6
4	1

1	2	3	4	5	6
4	1	3

1	2	3	4	5	6
	1	3

1	2	3	4	5	6
	1	3	8

1	2	3	4	5	6
		3	8

Exercises 10.1-4

---

Rewrite ENQUEUE and DEQUEUE to detect underflow and overflow of a queue.

Answer

Add at the beginning:

ENQUEUE(Q, x):
	if head[Q] == tail[Q] + 1
		then error "overflow"
	......
	
DEQUEUE(Q):
	if head[Q] == tail[Q]
		then error "underflow"
	......

Exercises 10.1-5

---

Whereas a stack allows insertion and deletion of elements at only one end, and a queue allows insertion at one end and deletion at the other end, a deque (double-ended queue) allows insertion and deletion at both ends. Write four O(1)-time procedures to insert elements into and delete elements from both ends of a deque constructed from an array.

Answer

我没有检查overflow和underflow,用N去判断就可以了.

implementation

Exercises 10.1-6

---

Show how to implement a queue using two stacks. Analyze the running time of the queue operations.

Answer

这个题目也出现在leetcode

my solution

最坏情况pop需要O(n),但是pop的平均情况只需要O(1)

Exercises 10.1-7

---

Show how to implement a stack using two queues. Analyze the running time of the stack operations.

Answer

这个题目有出现在leetcode，这是我的solution

• push操作是O(1)的
• empty操作是O(1)的
• top操作是O(1)的
• 但是pop操作最坏需要O(n)

---

Follow @louis1992 on github to help finish this task.