CLRS Chapter 10: Elementary Data Structures

Exercise 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.

The first stack starts at 1 and grows up towards n, while the second starts form n and grows down towards 1. Stack overflow happens when an element is pushed when the two stack pointers are adjacent.

Exercise 10.1.4
Also https://code.google.com/p/clrs/source/browse/ch10/10.1-4.py

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

I shall go with the pseudo-code version, since I'm too lazy to bother figuring out how to test it in C.

We need to do a slight modification, since the current version provides no way to tell whether a queue is empty or full. We should haveQ.head == NIL when the queue is empty and Q.head == Q.tail when the queue is full. An empty queue is initializes with NIL in its head andQ.tail =. We need to update Q.head when a DEQUEUE operation causes the queue to become empty.

https://github.com/Maeby/CLRS/blob/master/10.1-4

	typedef struct queue_ { uint head;
	uint tail;
	uint count;
	} queue_t;
	#define QUEUE_SIZE 10;
	static queue_t queue;
	static int array[QUEUE_SIZE]
	void
	queue_initialize (queue_t *Q)
	{
	uint i;
	memset(array, 0, sizeof(int) * QUEUE_SIZE);
	memset(queue, 0, sizeof(queue_t));
	}
	void
	ENQUEUE (queue_t *queue, int *array, int x)
	{
	/*
	* Check for overflow
	*/
	if (queue->count == QUEUE_SIZE) {
	printf("\nQueue Overflow");
	return;
	}
	if (queue->tail == QUEUE_SIZE - 1) {
	queue->tail = 0;
	} else {
	queue_tail++;
	}
	queue->count++;
	array[queue->tail] = x;
	}
	int
	DEQUEUE (queue_t *queue, int *array)
	{
	int x;
	/*
	* Check for underflow
	*/
	if (queue->count == 0) {
	printf("\nQueue Underflow");
	return (0);
	}
	x = array[queue->head];
	if (queue->head == QUEUE_SIZE - 1) {
	queue->head = 0;
	} else {
	queue->head++;
	}
	queue->count--;
	return (x);
	}

Exercise 10.2.1

Can you implement the dynamic-set operation INSERT on a singly linked list in O(1) time? How about DELETE?

You can implement INSERT in constant time by prepending it to the list.

You cannot implement DELETE in constant time, unless you pass to it as an argument the predecessor of the element you are deleting.

Exercise 10.2.2

Implement a stack using a singly linked list L. The operations PUSH and POP should still take O(1) time.

This is too simple to be worth implementing.

The PUSH operation adds an element in the beginning of the list and the POP operation removes the first element from the list.

http://clrs.skanev.com/10/02/03.html

Implement a queue by using a singly linked list L. The operations ENQUEUE and DEQUEUE should still take O(1) time.

\The ENQUEUE operation inserts an element in the beginning of the list and the DEQUEUE operation removes an element from the end of the list. In this case we need to keep track of the last element of the list. We can do that with a sentinel.

https://github.com/gzc/CLRS/blob/master/C10-Elementary-Data-Structures/10.1.md